#include <iostream>  
#include <chrono>  
#include <string>  
#include <random>  
#include "Mystring.hpp"  
#include "find_kmp.hpp"


// void Test1(){
//   Mystring str("hello world");
//   cout << str.c_str() << endl;
//   for(size_t i = 0; i<str.size(); ++i)
//   {
//     cout << str[i] << ' ' ;
//     ++str[i];
//   }
//   cout << endl;
//   cout << str.c_str() << endl; 
// }

// void Test2(){
//   Mystring str("Mystring");
//   Mystring copy(str);
//   Mystring::iterator it = copy.begin();
  
//   while(it!=copy.end())
//   {
//     cout << *it << " ";
//     ++*it;
//     ++it;
//   }
//   cout << endl;
//   for(auto e : copy)
//   {
//     cout << e;
//   }
//   cout << endl;
// }

// void Test3(){
//   Mystring str1 = "RuntimeError";
//   Mystring str2(str1);
//   Mystring str3;
//   str3 = str2;
//   cout << str1.c_str() << endl;
//   cout << str2.c_str() << endl;
//   cout << str3.c_str() << endl;
// }

// void Test4(){
//   Mystring str("hello");
//   str+=' ';
//   str+="world";
//   cout << str.c_str() <<endl;
//   str.insert(5, '#');
//   str.insert(0, '#');
//   cout << str.c_str() <<endl;
// }

// void Test5(){
//   Mystring str = "heo";
//   str.insert(2,"ll");
//   cout << str.c_str() << endl;
//   str.insert(str.size(), " world");
//   cout << str.c_str() <<endl;
//   str.insert(0, "Hi! ");
//   cout << str.c_str() <<endl;
//   str.insert(0, "");
//   cout << str.c_str() <<endl;
//   str.insert(1, "");
//   cout << str.c_str() <<endl;
// }

// void Test6(){
//   Mystring s1 = "hello";
//   Mystring s2 = "hello";
//   Mystring s3 = "hello";

//   s1.erase(2);
//   s2.erase(2, 20);
//   s3.erase(2,2);
//   cout << s1.c_str() << endl;
//   cout << s2.c_str() << endl;
//   cout << s3.c_str() << endl;
// }

// void Test7(){
//   Mystring s1;
//   Mystring s2 = "world";
//   cin >> s1;
//   cout << s1 << " " << s2 << endl;
//   Mystring s3("123");
//   s3+='\0';
//   s3+="456";
//   cout << s3.size() << endl;
//   cout << s3 << endl;
//   cout << s3[3]-0 << endl;
//   cout << s3.c_str() << endl;
// }

// void Test8(){
//   Mystring s1 = "abbbcdefg";
//   size_t pos1 = s1.find('b');
//   cout << pos1 <<endl; 
//   size_t pos2 = s1.Find_BF("bcd");
//   cout << pos2 <<endl;
//   size_t pos3 = s1.Find_BF("fg");
//   cout << pos3 <<endl;
//   Mystring s2 = "abcabc";
//   size_t pos4 = s2.find('b');
//   size_t pos5 = s2.find('b', 3);
//   cout << pos4 << " " << pos5 << endl;
// }

// void Test9(){
//   Mystring s1 = "12345";
//   Mystring s2(s1);
//   cout << (s1 == s2) << endl;
//   Mystring s3 = "123456";
//   cout << (s1 == s3) << endl;
//   cout << (s1 > s3) << endl;
//   cout << (s3 > s1) << endl;
//   Mystring s4("2345");
//   cout << (s3 > s4) << endl;
//   cout << (s4 > s3) << endl;
// }

// void Test10(){
//   Mystring s1;
//   cin >> s1 >> s1;
//   cout << s1 << endl;
// }

// void Test11(){
//   Mystring s1 = "hello";
//   s1+='\0';
//   s1+="world";
//   size_t pos = s1.Find_BF("world");
//   if(pos!=Mystring::npos)
//   {
//     cout << pos << endl;
//   }
//   else{
//     cout << "XXX" << endl;
//   }
// }

// void Test12(){
//   string s1 = "hello";
//   s1+='\0';
//   s1+="world";
//   for(size_t i = 0; i< s1.size(); ++i)
//   {
//     cout <<s1[i] << " ";
//   }
//   cout << endl;
//   string s2 = "helloworld";
//   for(size_t i = 0; i< s2.size(); ++i)
//   {
//     cout <<s2[i] << " ";
//   }
//   cout << endl;
// }

// void Test13(){
//   string s1 = "hello";
//   for(size_t i = 0; i< s1.size(); ++i)
//   {
//     cout <<s1[i] << " ";
//   }
//   cout << endl;
//   s1.insert(0, "");
//   s1.insert(1, "");
//   s1.insert(2, "");
//   for(size_t i = 0; i< s1.size(); ++i)
//   {
//     cout <<s1[i] << " ";
//   }
//   cout << endl;

// }

void Test_KMP1()
{
  Mystring target("abbabbababaaababaaa");
  Mystring model("ababaaababaa");
  int pos = target.Find_KMP(model);
  for(int i = pos; i < pos+model.size(); ++i)
  {
    cout << target[i];
  }
  cout << endl;
}



int BF_VS_KMP1() {  
    std::default_random_engine generator;  
    std::uniform_int_distribution<int> distribution(97, 122);  // ASCII码表中小写字母的范围  

    int num_tests = 10;  // 执行100次测试  
    int text_length = 100000;  // 文本长度为1000个字符  
    int pattern_length = 10000;  // 模式长度为100个字符  

    Mystring mystr;  
    Mystring pattern, text; 

    int time1 = 0, time2 = 0;

    for (int i = 0; i < num_tests; ++i) {  
        // 随机生成文本和模式字符串  
        for (int j = 0; j < text_length; ++j) {  
            text.push_back(distribution(generator));  
        }  
        for (int j = 0; j < pattern_length; ++j) {  
            pattern.push_back(distribution(generator));  
        }  

        mystr = text;  

        auto start_time = clock();  
        mystr.Find_BF(pattern);  
        auto end_time = clock();  
        auto duration_bf = end_time-start_time;  
        time1 += duration_bf;

        start_time = clock(); 
        mystr.Find_KMP(pattern);  
        end_time = clock(); 
        auto duration_kmp = end_time-start_time;  
        time2+= duration_kmp;
        
    }  
    std::cout << "朴素算法执行时间: " << time1 << " 微秒, KMP算法执行时间: " << time2 << " 微秒" << std::endl;  

    return 0;  
}

void Test_KMP2()
{
  string target("abbabbababaaababaaa");
  string model("ababaaababaa");
  int pos = Find_KMP(target, model);
  for(int i = pos; i < pos+model.size(); ++i)
  {
    cout << target[i];
  }
  cout << endl;
}



int BF_VS_KMP2() {  
    std::default_random_engine generator;  
    std::uniform_int_distribution<int> distribution(97, 122);  // ASCII码表中小写字母的范围  

    int num_tests = 100;  // 执行100次测试  
    int text_length = 1000;  // 文本长度为1000个字符  
    int pattern_length = 100;  // 模式长度为100个字符  

    string mystr;  
    string pattern, text; 

    int time1 = 0, time2 = 0;

    for (int i = 0; i < num_tests; ++i) {  
        // 随机生成文本和模式字符串  
        for (int j = 0; j < text_length; ++j) {  
            text.push_back(distribution(generator));  
        }  
        for (int j = 0; j < pattern_length; ++j) {  
            pattern.push_back(distribution(generator));  
        }  

        mystr = text;  

        auto start_time = clock();  
        Find_BF(mystr, pattern);
        auto end_time = clock();  
        auto duration_bf = end_time-start_time;  
        time1 += duration_bf;

        start_time = clock(); 
        Find_KMP(mystr, pattern);  
        end_time = clock(); 
        auto duration_kmp = end_time-start_time;  
        time2+= duration_kmp;
        
    }  
    std::cout << "朴素算法执行时间: " << time1 << " 微秒, KMP算法执行时间: " << time2 << " 微秒" << std::endl;  

    return 0;  
}

int main(){
  Test_KMP2();
  BF_VS_KMP2();
  return 0;
}

